#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
using ll=long long;
const int N=1e5+10;

vector<pair<int,int>> edge[N];

int n,k;
int dist[N];
int cnt[N],stg[N];
stack<int> st;
bool spfa()
{
	memset(dist,-0x3f3f3f,sizeof(dist));
	st.push(0);
	dist[0]=0;
	stg[0]=1;
	while(st.size())
	{
		int t=st.top();
		st.pop();
		stg[t]=0;
		for(auto& e:edge[t])
		{
			int x=e.first;
			int w=e.second;
			if(dist[x]<dist[t]+w)
			{
				dist[x]=dist[t]+w;
				cnt[x]=cnt[t]+1;
				if(cnt[x]==n+1)
					return false;
				if(stg[x]==0)
				{
					st.push(x);
					stg[x]=1;
				}
			}
		}
	}
	return true;
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<k;i++)
	{
		int x,a,b;
		scanf("%d%d%d",&x,&a,&b);
		if(x==1)
		{
			edge[b].push_back({a,0});
			edge[a].push_back({b,0});
		}
		else if(x==2)
		{
			edge[a].push_back({b,1});
		}
		else if(x==3)
		{
			edge[b].push_back({a,0});
		}
		else if(x==4)
		{
			edge[b].push_back({a,1});
		}
		else if(x==5)
		{
			edge[a].push_back({b,0});
		}
		
	}
	for(int i=1;i<=n;i++)
	{
		edge[0].push_back({i,1});
	}
	
	if(!spfa())
	{
		cout<<-1<<endl;	
	}
	else{
		ll ret=0;
		for(int i=1;i<=n;i++)
			ret+=dist[i];
		cout<<ret<<endl;	
	}
	return 0;
}
